#include<iostream>
#include<cstring>
#include<queue>
// #define ONLINE_GUDGE
using namespace std;
const int N = 1010, M = N * N, INF = 0x3f3f3f3f;

#define x first
#define y second 
using PII = pair<int, int>;
using PIII = pair<int ,PII>;
int n,m,S,T,K;  // S -(K)->T
int h[N], rh[N], e[M], w[M], ne[M], idx; // head  reverse_head(双向bfs) egde weight next
int dist[N], cnt[N]; // 估价值 记录每个点被更新的次数
bool st[N]; // 


void add_edge(int h[], int a, int b, int c)
{e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; }

void dijkstra() // 计算每个点到终点T的最短距离
{
    priority_queue<PII, vector<PII>, greater<PII>> heap; // dist vertex
    heap.push({0, T}); // 起点入队

    memset(dist, INF, sizeof dist);
    dist[T] = 0;

    while(heap.size())
    {
        auto t = heap.top(); heap.pop();

        int u = t.y;
        if(st[u]) continue; // 已遍历
        st[u] = true;

        for(int i = rh[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i]){ // 可以更新
                dist[v] = dist[u] + w[i];
                heap.push({dist[v], v});
            }
        }
    }
}

int Astar()
{
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap; // 估价值 起点->u 编号
    heap.push({dist[S], {0, S}});

    memset(st, 0, sizeof st);

    while(heap.size())
    {
        auto t = heap.top(); heap.pop();

        int u = t.y.y, real_distance = t.y.x;
        cnt[u]++;
        if(cnt[T] == K) return real_distance;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
           // 该点到j点的路径还没被更新K次，就将该点加入队列，减少遍历次数
            if(cnt[v] < K) // 出队次数<K 需要更新
                heap.push({real_distance +w[i]+dist[v], {w[i]+real_distance, v}}); // 估价函数值为到该点的距离加上该点到j点的距离加上j点到终点T的距离
        }
    }

    return -1; // 如果找不到第K短路，返回-1
}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
    freopen("./in.txt","r",stdin);
    #endif
    ios::sync_with_stdio(false);   
	cin.tie(0);

    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for(int i = 0;i < m; i++)
    {
        int a,b,c; 
        cin >> a >> b >> c;
        add_edge(h, a, b, c);
        add_edge(rh, b, a, c);
    }

    cin >> S >> T >> K;
    if(S == T) K++;

    dijkstra();

    printf("%d\n", Astar());
    
    return 0;
}